#include <vector>
#include <functional>
#include <string.h>
using namespace std;

template <class T, class Compare>
void _merge_sort(vector<T>& vc, int begin, int end, vector<T>& tmp, Compare comp){
  int mid = begin+(end-begin)/2;
  int begin1 = begin;
  int end1 = mid;
  int begin2 = mid;
  int end2 = end;
  if(end1-begin1 > 1) _merge_sort(vc,begin1,end1,tmp,comp);
  if(end2-begin2 > 1) _merge_sort(vc,begin2,end2,tmp,comp);
  int i = begin1;
  while(begin1 < end1 && begin2 < end2)
  {
    if(comp(vc[begin1], vc[begin2]))
    {
      tmp[i++] = vc[begin1++];
    }
    else{
      tmp[i++] = vc[begin2++];
    }
  }
  while(begin1 < end1)
  {
      tmp[i++] = vc[begin1++];
  }
  while(begin2 < end2)
  {
      tmp[i++] = vc[begin2++];
  }

  for(int j = begin; j<end; ++j)
  {
    vc[j] = tmp[j];
  }
}

//template <class T, class Compare>
//void merge_sort(vector<T>& vc, Compare comp = less<T>()){
//  vector<T> tmp;
//  tmp.resize(vc.size());
//  _merge_sort(vc, 0, vc.size(), tmp, comp);
//}

template <class T, class Compare>
void merge_sort(vector<T>& vc, Compare comp = less<T>()){
  vector<T> tmp;
  tmp.resize(vc.size());
  int gap = 1;
  while(gap < vc.size())
  {
    for(int left = 0; left<vc.size(); left+=2*gap)
    {
      int begin1 = left;
      int end1 = begin1+gap;
      int begin2 = end1; 
      int end2 = begin2+gap;

      int i = begin1;
      if(end1 >= vc.size())
      {
        //不需要排序但要写入tmp
        //end1 = vc.size();
        //while(begin1 < end1)
        //{
        //    tmp[i++] = vc[begin1++];
        //}
        break;
      }

      if(end2 > vc.size())
      {
        //调整后归并排序
        end2 = vc.size();
      }
      
      while(begin1 < end1 && begin2 < end2)
      {
        if(comp(vc[begin1], vc[begin2]))
        {
          tmp[i++] = vc[begin1++];
        }
        else{
          tmp[i++] = vc[begin2++];
        }
      }

      while(begin1 < end1)
      {
          tmp[i++] = vc[begin1++];
      }
      while(begin2 < end2)
      {
          tmp[i++] = vc[begin2++];
      }

      for(int j = left; j<end2; ++j)
      {
        vc[j] = tmp[j];
      }
    }
    vc = tmp;
    gap *= 2;
  }
}
